package MaximumXorWithAnElementFromArray_1707;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/maximum-xor-with-an-element-from-array/description/
 * <p>
 * 给你一个由非负整数组成的数组 nums 。另有一个查询数组 queries ，其中 queries[i] = [xi, mi] 。
 * 第 i 个查询的答案是 xi 和任何 nums 数组中不超过 mi 的元素按位异或（XOR）得到的最大值。换句话说，答案是 max(nums[j] XOR xi)
 * ，其中所有 j 均满足 nums[j] <= mi 。如果 nums 中的所有元素都大于 mi，最终答案就是 -1 。
 * <p>
 * 返回一个整数数组 answer 作为查询的答案，其中 answer.length == queries.length 且 answer[i] 是第 i 个查询的答案。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [0,1,2,3,4], queries = [[3,1],[1,3],[5,6]]
 * <p>
 * 输出：[3,3,7]
 * <p>
 * 解释：
 * <p>
 * 1) 0 和 1 是仅有的两个不超过 1 的整数。0 XOR 3 = 3 而 1 XOR 3 = 2 。二者中的更大值是 3 。
 * <p>
 * 2) 1 XOR 2 = 3.
 * <p>
 * 3) 5 XOR 2 = 7.
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums = [5,2,4,6,6,3], queries = [[12,4],[8,1],[6,3]]
 * <p>
 * 输出：[15,-1,5]
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length, queries.length <= 105
 * queries[i].length == 2
 * 0 <= nums[j], xi, mi <= 109
 */
public class Solution {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(maximizeXor(new int[]{0, 1, 2, 3, 4}, new int[][]{new int[]{3, 1}, new int[]{1, 3}, new int[]{5, 6},})));
        System.out.println(Arrays.toString(maximizeXor(new int[]{5, 2, 4, 6, 6, 3}, new int[][]{new int[]{12, 4}, new int[]{8, 1}, new int[]{6, 3},})));
    }

    public static int[] maximizeXor(int[] nums, int[][] queries) {
        int[] target = new int[queries.length];
        PreNode preNode = new PreNode();
        for (int num : nums) {
            preNode.add(num);
        }
        for (int i = 0; i < queries.length; i++) {
            target[i] = preNode.compare(queries[i][0], queries[i][1]);
        }
        return target;
    }
}

class PreNode {
    Node head = new Node();

    void add(int num) {
        Node cur = this.head;
        cur.min = Math.min(num, cur.min);
        for (int move = 30; move >= 0; move--) {
            int path = (num >> move) & 1;
            cur.next[path] = cur.next[path] == null ? new Node() : cur.next[path];
            cur = cur.next[path];
            cur.min = Math.min(num, cur.min);
        }
    }

    int compare(int num, int limit) {
        Node cur = this.head;
        if (limit < cur.min) {
            return -1;
        }
        int target = 0;
        for (int move = 30; move >= 0; move--) {
            int path = (num >> move) & 1;
            int best = path ^ 1;
            if (cur.next[best] == null || cur.next[best].min > limit) {
                best = best ^ 1;
            }
            target |= (path ^ best) << move;
            cur = cur.next[best];
        }
        return target;
    }
}

class Node {
    final Node[] next = new Node[2];
    int min = Integer.MAX_VALUE;
}
